package traverse

import "../binarytree"

type TreeNode = binarytree.TreeNode

// 实现二叉树的先序遍历
// 递归版本
func preOrder(root *TreeNode) []int {
	var res []int
	preOrderHelper(root, &res)
	return res
}

func preOrderHelper(root *TreeNode, res *[]int) {
	if root != nil {
		// 先访问当前节点
		*res = append(*res, root.Val)
		// 递归
		preOrderHelper(root.Left, res)
		preOrderHelper(root.Right, res)
	}
}

// 非递归
func preOrderNon(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	// 使用栈
	stack := []*TreeNode{root}
	var res []int

	for len(stack) > 0 {
		// 访问
		curNode := stack[len(stack)-1]
		stack = stack[:len(stack)-1] //出栈操作
		res = append(res, curNode.Val)
		if curNode.Right != nil {
			stack = append(stack, curNode.Right)
		}
		if curNode.Left != nil {
			stack = append(stack, curNode.Left)
		}
	}
	return res
}
